#include "tree.h"
#include <stdio.h>
#include <stdlib.h>

struct _node  {
	TDT key;
	TDT value;
	struct _node* left;
	struct _node* right;
};

typedef struct _node Node;

struct _tree {
	TreeInterface iface;
	Node* root;
	int replace;
};

int _insert_node(Tree* tree, Node** node, Pair* p) {
	Node* n = *node;
	if ( n == NULL ) {
		*node = (Node*)malloc(sizeof(Node));
		if ( ! (*node) )
			return -1;
		n = *node;
		tree->iface.clone_key(p->key, &(n->key));
		tree->iface.clone_value(p->value, &(n->value));
		n->left = NULL;
		n->right = NULL;
		return 0;
	} else {
		int cmp = tree->iface.compare_key(n->key, p->key);
		if ( cmp == 0 ) {
			if ( tree->replace ) {
				tree->iface.free_value(n->value);
				tree->iface.clone_value(p->value, &n->value);
				return 0;
			} else {
				if ( tree->iface.compare_value(n->value, p->value) ) {
					return _insert_node(tree, &n->left, p);
				}
			}
		} else if ( cmp < 0 ) {
			return _insert_node(tree, &n->left, p);
		} else {
			return _insert_node(tree, &n->right, p);
		}
	}
}


int tree_create(TreeInterface* iface, Tree** result) {
	*result = (Tree*) malloc(sizeof(Tree));
	if ( ! (*result) )
		return -1;
	(*result)->replace = 0;
	(*result)->iface = *iface;
	(*result)->root = NULL;
}

int tree_insert(Tree* tree, Pair* p) {
	return _node_insert(tree, &tree->root, p);
}

int _search_node(Tree* tree, Node* n, Pair* p, Pair* result,  Node** next) {
	if ( n == NULL ) {
		return -1;
	} else {
		int cmp = tree->iface.compare_key(n->key, p->key);
		if ( cmp == 0 ) {
			tree->iface.clone_key(n->key, &result->key);
			tree->iface.clone_value(n->value, &result->value);
			*next = n->left;
			return 0;
		} else if ( cmp < 0 ) {
			*next = n->left;
			return 1;
		} else {
			*next = n->right;
			return 1;
		}
	}
}


int tree_search(Tree* tree, Pair* p, int (*callback)(Pair* p, void* data), void* data) {
	int result = 0;
	Node* n = tree->root;
	while ( result >= 0 ) {
		Node* next;
		Pair r;
		result = _search_node(tree, n, p, &r, &n);
		if ( result == 0 ) {
			callback(&r, data);
		}
		n = next;
	}
	return 0;

}

int tree_remove(Tree* tree, Pair* p) {
	

}

